점근 표기법

1. 개요 및 정의

1.1. 연관된 표기법

2. 해석학에서의 활용법3. 컴퓨터 과학에서의 점근 표기법4. 참고5. 관련 문서

Asymptotic notation, 漸近表記法

1. 개요 및 정의 [편집]

수리과학의 여러 분야에서 함수의 증감 추세를 비교하는 표기법이다. 큰 O-표기법(Big-O notation), 란다우 표기법(Landau notation)이라 부르기도 한다.

점근 표기법(asymptotic notation)
실함수 $f,\,g: [0,\,\infty) \rightarrow \mathbb{R}$ 에 대해
상수 $M>0,\,c>0$ 가 존재하여 $x>M \Rightarrow |f(x)| \le c g(x)$ 를 만족시킬 때, 이를 " $x \rightarrow \infty$ 에 대해 $f(x) = O(g(x))$ "라 표기한다.
상수 $\epsilon>0,\,c>0$ 가 존재하여 $|x-a|<\epsilon \Rightarrow |f(x)| \le c g(x)$ 를 만족시킬 때, 이를 " $x \rightarrow a$ 에 대해 $f(x) = O(g(x))$ "라 표기한다.

무한대 점근의 정의는 실수열

f,g : \mathbb{N} \rightarrow \mathbb{R}

에 대해서도 동일하게 정의될 수 있고, 이 편이 훨씬 많이 쓰인다.

수식 입력 편의상 이탤릭체를 사용하는 경우가 대부분이나, 흘림체인

\mathcal{O}

를 사용하는 경우도 많이 있다. 다만,

O

를 처음 사용한 버크만, 란다우의 서적이나 이를 컴퓨터 과학에 본격적으로 들여온 도널드 크누스의 노트도 딱히 글꼴을 지정하진 않았다.

1.1. 연관된 표기법 [편집]

크누스는 란다우의 표기법을 종합해 다음의 4가지 표기법을 같이 정리하였다.

$f(x) = o(g(x))$ : 임의의 $c>0$ 에 대해 $M$ 이 존재하여 $x>M \Rightarrow |f(x)| \le c g(x)$
$f(x) = \Omega(g(x))$ : $M,c>0$ 이 존재하여 $x>M \Rightarrow |f(x)| > c g(x)$
$f(x) = \omega(g(x))$ : 임의의 $c>0$ 에 대해 $M$ 이 존재하여 $x>M \Rightarrow |f(x)| > c g(x)$
$f(x) = \Theta(g(x))$ : $f(x)>0$ 중에서 $f(x)=O(g(x))$ 이며 $f(x)=\Omega(g(x))$

극미한 접근(

x \rightarrow a

)의 경우도 비슷하게 정의할 수 있다.

이외에도 점근을 나타내는 다음의 다양한 표기가 있다.

표기 $f \ll g$ 는 $f=O(g)$ 와 동치이다.
표기 $f \asymp g$ 는 $f = \Theta(g)$ 와 동치이다.
표기 $f \sim g$ 는 $\lim_{x\to\infty}\limits (f/g)=1$ 과 동치이다.

2. 해석학에서의 활용법 [편집]

극한과 비슷하게 생각할 수 있지만 세부적인 성질은 달라지는 것들이 많다. 예를 들어서

\lim_{x\to\infty}\limits \left|\dfrac fg\right| < \infty \Rightarrow f = O(g)

이 명제의 역은 성립하지 않는데,

(f,\,g) = (\sin(x),\,1)

같은 예시처럼 극한이 진동할 수도 있기 때문이다. 다만, 다음은 성립한다.

\displaystyle f =O(g) \Leftrightarrow \limsup \left| \frac{f}{g} \right| < \infty

\displaystyle

해석학에서의 점근 표기법은 단순히

f=O(g)

꼴 뿐만이 아니라 굉장히 자유롭게 쓰이는데, 예를 들어서

\displaystyle \sum_{i=1}^N \frac1i = \log N + \gamma + O(N^{-1})

(

N \rightarrow \infty

일 때)

혹은

e^x = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots + \dfrac{x^k}{k!} + O(x^{k+1})

(

k

는 고정된 자연수이고

x \rightarrow 0

일 때)

와 같은 표기법은 좌우변의 차이인 오차항이 O-표기법을 따르는 함수라는 것을 의미한다. 이런 표기법이 빈번하게 쓰이는 이유 중 하나는 O-표기법이 사칙연산에 비해 비교적 잘 행동하기 때문이다. 예를 들어서

f_1 = O(g_1)

,

f_2=O(g_2)

이면

f_1 + g_1 = O(g_1+g_2)

,

f_1 f_2 = O(g_1 g_2)

등이 성립한다. 다만, 사칙연산에 대해서만 성립할 뿐이고,

e^f = O(e^g)

등이 성립하지는 않는다. 이런 경우에는

f=e^{O(x)}

같은 표현이 쓰이는데, 이는

g=O(x)

인 함수

g

가 존재해서

f = e^g

가 된다는 것을 의미한다.

O-표기법은 다변수함수, 벡터함수, 복소함수 등에서 쓰이기도 한다. 예를 들어서, 다변수 테일러 정리의 표현식을 다음처럼 쓸 수 있다.

\displaystyle f(x+h) = \sum_{|\alpha| \le m} \frac{\partial^{\alpha} f(x)}{\alpha_1! \cdots \alpha_n!}h^{\alpha} + O(\|h\|^{m+1})

3. 컴퓨터 과학에서의 점근 표기법 [편집]

일반적으로 알고리즘의 시간복잡도를 나타내는데 사용된다. Big-O 표기법은 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간복잡도를 가진다는 의미이다. 물론 공간복잡도에 대해서도 사용될 수 있다.

프로그램을 돌렸을 때, 프로그램이 돌아가는 정확한 단계(step)의 수를 결정하는 작업은 매우 어렵다. 단계 수를 정확히 결정하는 데 드는 비용은 '단계'의 개념 자체가 부정확하기 때문에 낭비를 초래할 수 있다.[1] 그런데, 입력 데이터 개수

n

에 대해 두 프로그램의 단계 차이가

5n+7

이라든가

n^2+25

인 경우는 비교의 가치가 생긴다. 그러나, 이 경우에도 마찬가지로 굳이 사용자가

5n+7

이라는 것을 정확히 알기 보다는 그냥

5n

정도라고 생각해도 되지 않을까?

n

이 10억 정도라면 반드시 '예, 이 프로그램은 10억 개를 넣으면 50억 7개의 스텝을 진행합니다.'라고 얘기해야 하는가? 그냥 '대략

5n

정도 필요하구나' 하고 인식하면 충분히 큰

n

에 대해서는 그게 그거라는 것을 알 수 있다. 마찬가지로, 굳이

5n

이라고 하기보다는 '아,

n^1

에 비례하는구나,

n^2

에 비례하는구나' 정도로 생각해도 충분하다는 것이다.

결국, 정의와 연관시켜서 생각하면,

O(5n+7)=O(5n)=O(n)

이 되고,

O(n^2+25)=O(n^2)

이 된다는 뜻이다. 여기서 등호 기호(

=

) 기호를 '같다(equals)'가 아니라 '~이다(is)', '~쯤 된다'라고 해석하면 기호의 혼란을 피할 수 있다. 경우에 따라

O(g(n))

을 하나의 집합으로 보고

f(n) \in O(g(n))

으로 표기하기도 한다.[2]

파일:2-4-1.png
<파이썬 알고리즘 인터뷰> p.100, 책만, 2020

간단한 예를 한번 들어보자. 디스크에 있는 파일을 다른 지역에 살고 있는 친구에게 보낸다고 가정해보자. 그림에서 파일 크기가 작다면, 즉

n

이 작다면

O(n)

의 시간이 걸리는 온라인 전송이 빠르다. 하지만 파일이 아주 크다면 비행기를 통해 물리적으로 배달 하는게 더 빠를 수 있다(비용은 고려하지 않는다면).[3] 파일이 아무리 커도, 즉

n

이 아무리 커도 비행기를 통한 파일 전송은

O(1)

로 항상 일정한 시간이 소요되기 때문이다. 이것이 바로 점근적 실행 시간이며, 빅오는 점근적 실행 시간을 표기하는 방법 중 하나다.

4. 참고 [편집]

5. 관련 문서 [편집]

[1] 명령문

x=y

와

x=y+z+(x/y)+(x*y*z-x/z)

는 둘 다 한 단계로 간주한다.[2] 대다수의 알고리즘 원서가 이 집합(set)개념을 사용하고 있다. 보다 수학적으로 엄밀해지고, asymptotic tight bound을 정확히 특정하는 Big-θ 표기법에서는

\theta(g(n))

을 간단히

O(g(n))\cap\Omega(g(n))

으로 정의할 수 있다.

f(n)=O(g(n))

에서 등호는

\in

의 의미를 imply하며 동시에 직관성을 얻는다. 이 '같다'의 직관성은 Big-O notation의 오용을 초래했고, Big-Theta notation을 탄생하게 한 배경이 되었다.[3] 실제로 구글등의 PB단위로 데이터를 취급하는 단체,업체들이 이렇게 데이터를 항공운반 하는경우가 자주 있다.